1. Technical Field
The present invention relates to a technique for causing a server device to execute a process in response to a request from a client device and a server device.
2. Background Information
In recent years, a variety of communication services which utilize the Internet have come into use. One example of a communication protocol which is used for sending and receiving data over the Internet is TCP (Transmission Control Protocol). TCP is a connection-type communication protocol which enables highly reliable data communication to be carried out over the Internet. Under TCP, a data transmitting device (hereinafter, “server device”) and a data receiving device (hereinafter, “client device”) exchange connection data (hereinafter, “connection identifier”) prior to transmission of content data. The exchanged connection identifier is used to specify a communication path (hereinafter, “connection”) to thereby establish a connection for transmission of content data. Examples of connection identifiers include: a communication address assigned to a server device or a client device; data indicating a communication port (e.g. a communication port number) used by the devices for respectively transmitting and receiving data; or an initial value of a sequence number. Under TCP, a connection is established using a procedure referred to as a “3-way handshake”. A general description of this procedure follows.
FIG. 10 provides an overview of a 3-way handshake executed by a server device 40A and a client device 50A. Each of the devices is capable of communicating under TCP. It is assumed for the purposes of this explanation that a user who wishes to obtain content data from server device 40A performs a predetermined operation such as inputting data (e.g., URL) representing a communication address of server device 40A and a communication protocol to be used for acquiring the desired content data. Client device 50A first transmits to server device 40A a SYN message 200, as shown in FIG. 10. SYN message 200 is used for requesting establishment of a connection when data is to be transmitted from server device 40A to client device 50A (hereinafter, “downlink connection”); and the message includes a connection identifier for the downlink connection.
Server device 40A, upon receiving SYN message 200, allocates a computer resource (hereinafter, “resource”) for establishing a connection with the source of the SYN message 200, client device 50A. Specifically, server device 40A writes, in a memory device such as RAM (Random Access Memory), and data (e.g., a connection identifier of the downlink connection mentioned above) for identifying a correspondent device (i.e., client device 50A). Server device 40A then transmits to client device 50A a SYN/ACK message 210 indicating receipt of SYN message 200, and also transmits a request for establishing a connection in the reverse direction (hereinafter, “uplink connection”). The uplink connection is used when data is transferred from client device 50A to server device 40A; and the SYN/ACK message 210 includes a connection identifier for the uplink connection. Server device 40A retransmits SYN/ACK message 210 by referring to stored data in the memory device in a case that a message acknowledging a receipt of SYN/ACK message 210 (hereinafter, “ACK”) is not received within a predetermined time since the transmission of the message 210.
Client device 50A, upon receiving SYN/ACK message 210, reads the connection identifier in the SYN/ACK message 210 and establishes a connection (i.e., the uplink connection) in accordance with the connection identifier. Client device 50A then transmits to server device 40A an ACK 220 indicating receipt of the SYN/ACK message 210. ACK 220 includes a connection identifier for the downlink connection. Upon receiving ACK 220, server device 40A establishes the uplink connection identified by the connection identifier included in ACK 220, deletes data identifying the correspondent device from the memory device, and awaits receipt of a message transmitted through the downlink connection from the client device 50A, such as a request for transmitting data (e.g., a message containing a HTTP GET method).
It is to be noted that since resources of server device 40A, such as a capacity of a memory device, are limited, a number of connection identifiers (i.e., data indicating a correspondent device with which a connection is about to be established) which can be stored in the memory device is also accordingly limited. Thus, a number of ACKs 220 from client devices 50A for which server device 40A can wait is limited to a number of connection identifiers which can be retained at the server. It is this limitation that makes a server vulnerable to abuse. Namely, a denial of service attack can be launched against the server by a malicious client device by sending from the device a large number of SYN messages 200 to the server for queuing, thereby exhausting the resources of the server. Such an attack is referred to as a “SYN Flood Attack.”
When a SYN Flood Attack is launched, a malicious client device which is the source of the attack continuously transmits a large number of SYN messages 200 to server device 40A. When the server sends or attempts to send responsive SYN/ACK messages 210 no ACK 220 is forthcoming from the client device. The server therefore retains for a set time period data identifying a correspondent device, assuming that a connection between the correspondent device is not yet established, and awaits an ACK 220. When a SYN Flood Attack is attempted, a number of connection identifiers queued at the server soon reaches an upper limit. As a result, the server device is no longer able to accept connection requests from client devices; and communication services cannot be provided.
Various methods have been proposed for dealing with SYN Flood Attacks. They include a client puzzle protocol disclosed in Ari Juels and John Brainard (RSA Labs), “Client Puzzles: A Cryptographic Defense Against Connection Depletion Attacks”, and a client puzzle auction disclosed in XiaoFeng Wang, Michael K. Reiter, “Defending Against Denial-of-Service Attack with Puzzle Auctions”, Proceedings of the 2003 IEEE Symposium on Security and Privacy, 2003. In the following, description will be given of these techniques with reference to the attached figures.
FIG. 11 is a diagram providing an overview of a client puzzle protocol. In the figure, a server device 40B and a client device 50B are communication devices which establish a connection according to the client puzzle protocol. Server device 40B differs from server device 40A of FIG. 10 in that the device 40B does not store data showing a source of SYN message 100 upon reception, and that the device 40B transmits, upon receiving SYN message 100, transmits a message (a RST/ACK message 101 of FIG. 11) requesting execution of a predetermined computation and a reply including a result of the computation. RST/ACK message 101 includes data representing the predetermined computation (hereinafter, “client puzzle”).
Client device 50B, upon receiving RST/ACK message 101, performs a computation designated by the client puzzle contained in RST/ACK message 101, and transmits to server device 40B a SYN message 102 after writing a computation result in the message. In the following, execution of a computation designated by a client puzzle will be referred to as “to solve a client puzzle,” and a computation result as “a solution of a client puzzle.” When server device 40B receives SYN message 102, it determines whether the solution contained in SYN message 102 is correct; and the device 40B establishes a connection between client device 50B in accordance with a procedure that is the same as that employed in a 3-way handshake method, only when the solution is determined to be correct.
Thus, server device 40B transmits a client puzzle to client device 50B which has requested establishment of a connection, and does not establish a connection until the correct solution of the client puzzle is returned from client device 50B. A client device attempting a SYN Flood Attack on server 40B by transmitting a large number of SYN messages can no longer continue the attack unless it submits to server device 40B a correct solution to a client puzzle returned from the server as a response to each SYN message. To continue a SYN Flood Attack on server 40B, a client device has to solve a number of client puzzles, which means that the client device must have large resources available for computation. Consequently, the client device becomes incapable of continuing to transmit SYN messages. Thus, according to the client puzzle protocol, a SYN Flood Attack can be effectively handled.
A crucial factor in implementing the client puzzle protocol is that an amount of computation designated by a client puzzle is appropriately tuned (“an amount of computation” will be hereinafter referred to as “client puzzle difficulty”). In a case that client puzzle difficulty is set too low, i.e., the computation amount is too small, it is possible for a client device to obtain a solution for a client puzzle by using relatively few resources; and as a consequence, a SYN Flood Attack cannot be defended against. Conversely, when client puzzle difficulty is too high, i.e., a computation amount is too large, it would take time even for a legitimate client device not attempting a SYN Flood Attack to solve a client puzzle; as a result, such a client device will have difficulty in utilizing a communication service provided by a server device.
In reality, however, it is not readily possible to tune an appropriate level of client puzzle difficulty suited for each client device in an existing communication system. Generally, there is used in an existing communication system a mixture of various client devices with different degrees of capability, such as personal computers and PDA (Personal Digital Assistance)s, but an appropriate level of client puzzle difficulty depends on the capability of each client device. The client puzzle auction proposed by Wang, et. al has provided, as its object, a solution for such a problem existing in the client puzzle protocol. Description is now given of the client puzzle auction.
FIG. 12 is a diagram for describing an overview of the client puzzle auction. A server device 40C and a client device 50C are communication devices which establish a connection according to the client puzzle auction. Client device 50C of FIG. 12 is adapted to transmit either one of first data or second data when transmitting a SYN message 102 (102a or 102b) containing an obtained solution of a client puzzle, the first data being a request for transmission for a client puzzle with higher difficulty and the second data being a request for not transmitting any more difficult client puzzle.
Server device 40C, when the first data is included in SYN message 102 received from client device 50C, generates a client puzzle with higher difficulty and transmits a RST/ACK message 101b containing the generated client puzzle. In a case where SYN message 102 received from client device 50C includes the second data, server device 40C initiates establishment of a connection according to a conventional 3-way handshake.
According to the client puzzle auction, server device 40C of FIG. 12, when it receives SYN messages 102 from a plurality of client devices, gives a higher priority to SYN message 102 including a solution for a client puzzle with higher level of difficulty when handling a request and establishes a connection preferentially with a client device which is the source of such a SYN message 102. Since generally large resources are consumed for solving a client puzzle with high level of difficulty, transmission frequency of connection open requests will be reduced. A higher priority is given as a compensation for a client device which has accepted a higher process burden and which is rendered capable of transmitting connection establishment requests less frequently. In other words, client server 50C must accept commitment of large resources if it wishes to have a connection open request it transmits to be handled by server device 40C with higher priority.
As described above, since committing large resources is an obstacle for a client device to perform a SYN Flood Attack, the client puzzle auction enables effective defense against a SYN Flood Attack. Further, since each client device 50C is enabled to receive a client puzzle suited for its own process capability and solve the puzzle, the above described problem existing in the client puzzle protocol is also solved. Thus, according to the client puzzle auction, a client device is enabled to shoulder a burden depending on its process capability, and a connection is established according to a priority corresponding to a burden each client device has accepted.
Nevertheless, when the client puzzle auction is used, a number of messages exchanged between a server device and a client device (hereinafter, “communication traffic”) is increased when compared with the conventional 3-way handshake and the client puzzle protocol, as obvious from what is shown in FIGS. 10, 11, and 12. Such an increase of communication traffic between a server device and a client device is not welcome, since it potentially becomes a factor for causing congestion in a communication network through which communication between the two devices is performed.